package com.leetcode.array;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 1. 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 *
 * @author gaowenjin
 * @date 2020/3/31
 * @description:
 */
public class TwoNumberSum {


    int[] nums1 = {2, 7, 11, 15};
    int target1 = 9;

    @Test
    public void twoSumByV1() {

        TwoNumberSum twoNumberSum = new TwoNumberSum();

        /************************1************************/

        int[] actualArr1 = twoNumberSum.twoSumByV1(nums1, target1);
        int[] expectedArr1 = {0, 1};

        Assert.assertArrayEquals(expectedArr1, actualArr1);

        System.out.println("第一轮测试：OK");

        /*************************2***********************/


        int[] nums2 = {2, 3, 3, 6};
        int target2 = 6;

        int[] actualArr2 = twoNumberSum.twoSumByV1(nums2, target2);
        int[] expectedArr2 = {1, 2};

        Assert.assertArrayEquals(expectedArr2, actualArr2);

        System.out.println("第二轮测试：OK");

        /**************************3**********************/

        int[] nums3 = {-2, -1, -4, -6};
        int target3 = -5;

        int[] actualArr3 = twoNumberSum.twoSumByV1(nums3, target3);
        int[] expectedArr3 = {1, 2};

        Assert.assertArrayEquals(expectedArr3, actualArr3);

        System.out.println("第三轮测试：OK");

        /***************************4*********************/


        int[] nums4 = {-2, -1, -4, 6};
        int target4 = 4;

        int[] actualArr4 = twoNumberSum.twoSumByV1(nums4, target4);
        int[] expectedArr4 = {0, 3};

        Assert.assertArrayEquals(expectedArr4, actualArr4);

        System.out.println("第四轮测试：OK");

    }

    /**
     * 暴力排序达到效果 时间复杂度 O(n2)
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSumByV1(int[] nums, int target) {

        for (int i = 0; i < nums.length; i++) {

            for (int j = i + 1; j < nums.length; j++) {

                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }

            }

        }

        throw new IllegalArgumentException("无符合元素");

    }

    @Test
    public void twoSumByHashMapV1() {

        TwoNumberSum twoNumberSum = new TwoNumberSum();

        /************************1************************/

        int[] actualArr1 = twoNumberSum.twoSumByHashMapV1(nums1, target1);
        int[] expectedArr1 = {0, 1};

        Assert.assertArrayEquals(expectedArr1, actualArr1);

        System.out.println("第一轮测试：OK");

        /*************************2***********************/


        int[] nums2 = {2, 3, 3, 6};
        int target2 = 6;

        int[] actualArr2 = twoNumberSum.twoSumByHashMapV1(nums2, target2);
        int[] expectedArr2 = {1, 2};

        Assert.assertArrayEquals(expectedArr2, actualArr2);

        System.out.println("第二轮测试：OK");

        /**************************3**********************/

        int[] nums3 = {-2, -1, -4, -6};
        int target3 = -5;

        int[] actualArr3 = twoNumberSum.twoSumByHashMapV1(nums3, target3);
        int[] expectedArr3 = {1, 2};

        Assert.assertArrayEquals(expectedArr3, actualArr3);

        System.out.println("第三轮测试：OK");

        /***************************4*********************/


        int[] nums4 = {-2, -1, -4, 6};
        int target4 = 4;

        int[] actualArr4 = twoNumberSum.twoSumByHashMapV1(nums4, target4);
        int[] expectedArr4 = {0, 3};

        Assert.assertArrayEquals(expectedArr4, actualArr4);

        System.out.println("第四轮测试：OK");

        /***************************5*********************/


        int[] nums5 = {3, 2, 4};
        int target5 = 6;

        int[] actualArr5 = twoNumberSum.twoSumByHashMapV1(nums5, target5);
        int[] expectedArr5 = {1, 2};

        Assert.assertArrayEquals(expectedArr5, actualArr5);

        System.out.println("第五轮测试：OK");

    }

    /**
     * 两遍哈希表 时间复杂度O(n)
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSumByHashMapV1(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap(nums.length * 2);

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int m = 0; m < nums.length; m++) {

            int mv = target - nums[m];

            if (map.containsKey(mv) && map.get(mv) != m) { // 排除自己
                return new int[]{m, map.get(mv)};
            }

        }

        throw new IllegalArgumentException("无符合元素");

    }

    @Test
    public void twoSumByHashMapV2() {

        TwoNumberSum twoNumberSum = new TwoNumberSum();

        /************************1************************/

        int[] actualArr1 = twoNumberSum.twoSumByHashMapV2(nums1, target1);
        int[] expectedArr1 = {0, 1};

        Assert.assertArrayEquals(expectedArr1, actualArr1);

        System.out.println("第一轮测试：OK");

        /*************************2***********************/


        int[] nums2 = {2, 3, 3, 6};
        int target2 = 6;

        int[] actualArr2 = twoNumberSum.twoSumByHashMapV2(nums2, target2);
        int[] expectedArr2 = {1, 2};

        Assert.assertArrayEquals(expectedArr2, actualArr2);

        System.out.println("第二轮测试：OK");

        /**************************3**********************/

        int[] nums3 = {-2, -1, -4, -6};
        int target3 = -5;

        int[] actualArr3 = twoNumberSum.twoSumByHashMapV2(nums3, target3);
        int[] expectedArr3 = {1, 2};

        Assert.assertArrayEquals(expectedArr3, actualArr3);

        System.out.println("第三轮测试：OK");

        /***************************4*********************/


        int[] nums4 = {-2, -1, -4, 6};
        int target4 = 4;

        int[] actualArr4 = twoNumberSum.twoSumByHashMapV2(nums4, target4);
        int[] expectedArr4 = {0, 3};

        Assert.assertArrayEquals(expectedArr4, actualArr4);

        System.out.println("第四轮测试：OK");

        /***************************5*********************/


        int[] nums5 = {3, 2, 4};
        int target5 = 6;

        int[] actualArr5 = twoNumberSum.twoSumByHashMapV2(nums5, target5);
        int[] expectedArr5 = {1, 2};

        Assert.assertArrayEquals(expectedArr5, actualArr5);

        System.out.println("第五轮测试：OK");

    }

    /**
     * 一遍哈希表 时间复杂度O(n)
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSumByHashMapV2(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap(nums.length * 2);

        for (int i = 0; i < nums.length; i++) {

            int mv = target - nums[i];

            if (map.containsKey(mv)) {
                return new int[]{map.get(mv), i};
            }

            map.put(nums[i], i);
        }

        throw new IllegalArgumentException("无符合元素");

    }

}
